package org.example.leetCode;

/**
 * 122. 买卖股票的最佳时机 II
 * 给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
 * 在每一天，你可以决定是否购买或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
 * 返回 你能获得的 最大 利润 。
 *
 */
public class Code122 {


    /**
     * 贪心算法
     * @param prices
     * @return
     */
    public static int maxProfit(int[] prices) {
        int maxProfit = 0;

        // 遍历价格数组，只要当天价格高于前一天，就进行交易
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i - 1]) {
                maxProfit += prices[i] - prices[i - 1]; // 累加利润
            }
        }

        return maxProfit;
    }

    /**
     * 动态规划
     * @param prices
     * @return
     */
    public int maxProfit1(int[] prices) {
        int[][] dp = new int[prices.length][2];
        // 0表示不持有股票，1表示持有股票
        dp[0][0] = 0;
        dp[0][1] = -prices[0];

        for(int i=1; i<prices.length; ++i){
            // 不持有股票的情况：
            // 1. 前一天也不持有股票（dp[i-1][0]）
            // 2. 前一天持有股票，今天卖出（dp[i-1][1] + prices[i]）
            dp[i][0] = Math.max(dp[i-1][1] + prices[i], dp[i-1][0]);

            // 持有股票的情况：
            // 1. 前一天就持有股票（dp[i-1][1]）
            // 2. 前一天不持有股票，今天买入（dp[i-1][0] - prices[i]）
            dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] - prices[i]);
        }

        return dp[prices.length-1][0]; // 最后一天不持有股票时的利润最大值
    }

    public static void main(String[] args) {
        int[] prices = {7, 1, 5, 3, 6, 4};
        System.out.println(maxProfit(prices)); // 输出: 7
    }
}


